package com.fzkj.sort;

import java.util.Arrays;

/**
 * 插入排序
 * @author yaya
 */
public class InsertionSort {

    /**
     * [34,8,64,51,32,21]
     * 插入排序的思想是将一个待排序元素插入到一个有序表中的合适位置。
     * 第一轮：
     *  1、34作为单独元素不需要排序
     *  2、选择待排序元素8插入到有序表[34]中合适位置 -> [8,34]
     *  3、选择待排序元素64插入到有序表[8,34]中合适位置 -> [8,34,64]
     *  ...
     */
    public static void main(String[] args) {
        int[] p = {34,8,64,51,32,21};
        insertionSort(p);
        System.out.println(Arrays.toString(p));
    }

    private static void insertionSort(int[] source){
        for (int i = 1; i < source.length; i++) {
            int step = 0;
            int temp = source[i];
            for (int j = i - 1; j >= 0; j--){
                if (temp < source[j]){
                    source[j + 1] = source[j];
                    source[j] = temp;
                    step++;
                }
            }
            System.out.println(step);
        }
    }

    private static void insertionSort2(int[] source){
        int j;
        for (int p = 1; p < source.length; p++) {
            int tmp = source[p];
            for (j = p; j > 0 && tmp < source[j - 1]; j--) {
                source[j] = source[j - 1];
            }
            source[j] = tmp;
        }
    }
}
